/*
有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶、3阶
请实现一个方法，计算小孩有多少种上楼的方式
为了防止溢出，请将结果Mod 1000000007

给定一个正整数int n，请返回一个数，代表上楼的方式数
保证n小于等于100000
 */

public class TakeTheStairs {

    // 模
    static final int mod = 1000000007;

    public static void main(String[] args) {
        System.out.println(recursionSolution(3));
        System.out.println(iterationSolution(4));
    }

    /**
     * 递归解法
     * 关于这个解法可能很多人很奇怪当stairs等于0的时候为什么也是1
     * 从整个递归思路来看，在最高位，每次往下踏3 2 1步，三种方式相对独立
     * 递归减少的是楼梯数，而最终要求的结果反而是走楼梯的方式数
     * 所以递归到最后剩下2阶的时候则直接返回2，因为此时下面只剩下两种方式(每次一步踏两次和一次踏两步)
     * 剩下1阶的时候也即只有一种方式，也即一次踏直接踏一阶，返回1
     * 剩下0阶的时候也是只有一种方式，那就是之前的台阶数在递归中刚好踏完了，同样返回1
     * @param stairs 总楼梯数
     * @return 上楼的方式数
     */
    public static int recursionSolution(int stairs) {
        if (stairs < 0) {
            return 0;
        }
        if (stairs == 0 || stairs == 1) {
            return 1;
        }
        if (stairs == 2) {
            return 2;
        }
        return recursionSolution(stairs - 1) % mod + recursionSolution(stairs - 2) % mod + recursionSolution(stairs - 3) % mod;
    }

    /**
     * 迭代(循环)解法
     * @param stairs 总楼梯数
     * @return 上楼的方式数
     */
    public static int iterationSolution(int stairs) {
        if (stairs < 0) {
            return 0;
        }
        if (stairs == 0 || stairs == 1) {
            return 1;
        }
        if (stairs == 2) {
            return 2;
        }
        if (stairs == 3) {
            return 4;
        }

        int x1 = 1;
        int x2 = 2;
        int x3 = 4;
        for (int i = 4 ; i <= stairs ; i++) {
            int temp = x1;
            x1 = x2 % mod;
            x2 = x3 % mod;
            x3 = ((x1 + x2) % mod + temp) % mod;
        }
        return x3;
    }

}
